#include <iostream>
#include <string>
#include <time.h>
#include "structures.h"
#include <QProgressBar>
#include <QApplication>
#include "ConstrArbre2.h"
#include <math.h>
dico2* ConstrArbre2(char *chaine, QProgressBar* bar,float *temps)
{
/*Cette fonction prend comme parametre une chaine et renvoie l'adresse de l'arbre qui correspond a cette chaine.. l'arbre etant construit dans cette fonction*/

	unsigned int j,av,pourcent=0;//j correspond a l'indice dans le tableau de pointeur, il est calcule par convert_car().av correspond a l'indice de la chaine a partir
	// de laquelle on doit creer une branche et pourcent me permet d'afficher le pourcentage d'évolution
	clock_t
	temps_initial, temps_final;
	float temps_cpu; 
	dico2 *Racine,*Noeud;//On cree un pointeur de type dico
	temps_initial = clock ();
	creernoeud2(&Racine);//on cree un noeud sur le pointeur
	for(unsigned int i=0;i<strlen(chaine);i++)//On construit l'arbre en testant toutes les combinaisons de caracteres
	{	
		
		if((i*100)/strlen(chaine)!=pourcent)
		{
			
			
			pourcent=(i*100)/strlen(chaine);
			bar->setValue(pourcent);
			bar->repaint();
			bar->update();
			bar->update();
			bar->update();
			QApplication::processEvents();
		}
		Noeud=Racine;
		av=Recherche(&Noeud,chaine,i);//On recherche le noeud ou l'on va creer la chaine
		j=convert_car(chaine[av]);
		
		creernoeud2(&(*Noeud).fils[j]);
		
		(*(*Noeud).fils[j]).DebutRacine=i+1;
		(*(*Noeud).fils[j]).debut=av+1;
		(*(*Noeud).fils[j]).taille=strlen(chaine)-av;
		
		
		
	
	}
	temps_final = clock ();

	temps_cpu = (temps_final - temps_initial) ;
	
	
	*temps=(temps_cpu)/CLOCKS_PER_SEC;
		return Racine;//On renvoie le pointeur vers la variable qui "attend" l'arbre
}
int Recherche(dico2** Racine,char* chaine,unsigned int av)
{
/*Cette fonction prend comme parametre une chaine, l'indice ou commence la chaine et un noeud d'un arbre..
Elle renvoie l'indice de la chaine qui doit etre creer. le noeud est egalement modifie par celui ou doit etre cree la branche car c'est un pointeur*/
	int j,aVinf=0;//aVinf correspond a avancement inférieur, c'est l'endroit de la chaine qui correspond a la branche ou on est situe (branche deja presente)
	//alors que av correspond a l'endroit de la chaine qui servira a construire la futur branche
	
	while(av<strlen(chaine))
	{
		
		j=convert_car(chaine[av]);
		
		if((**Racine).fils[j]!=NULL)//si il existe une branche qui correspond a cette suite de caractère on y va
		{
			aVinf=(*(**Racine).fils[j]).debut-1;
			while(aVinf-(*(**Racine).fils[j]).debut+1<(*(**Racine).fils[j]).taille  && chaine[aVinf]==chaine[av])
			{
				aVinf++;av++;// on avance dans la branche
			}
			if ((*(**Racine).fils[j]).taille<=aVinf-(*(**Racine).fils[j]).debut+1)//Si on a atteint la fin de la branche on change de noeud
			{
			*Racine=(**Racine).fils[j];
			}
			else//sinon c'est que la branche décrivant notre suite de caractere n'existe pas, donc on cree un noeud a cette endroit
			{	
				CoupeArc2(&(**Racine).fils[j],aVinf,chaine);
				(*(**Racine).fils[j]).pere=(*Racine);
				*Racine=(**Racine).fils[j];//on se positionne sur le noeud
				return av;//on renvoit le debut de la suite de caractere qui correspondra a la futur branche
			}
		}
		else
		{
		return av;//si il n'existe pas de branche presentant la suite de caractere, on renvoit le debut de la chaine qui correspondra a la futur branche
		}
		
	}
	return av;
}

void creernoeud2(dico2 **racine)
{/*Cette fonction correspond au constructeur qu'on pourrait trouver dans un objet en C, il regle les attributs et alloue l'espace memoire necessaire,
il ne renvoie rien*/
	*racine=(dico2*)malloc(sizeof(dico2));//On alloue la memoire pour le noeud
	for(int i=0;i<6;i++)
	{
		(*(*racine)).fils[i]=NULL;//et on initialise les valeurs du noeud
	}
	(*(*racine)).debut=0;
	(*(*racine)).taille=0;
	(*(*racine)).DebutRacine=0;
}
void CoupeArc2(dico2** Racine,int i, char *lettre)
{
/* La fonction prend en parametre la position dans la chaine, i, a partir d'ou les differentes chaines se separent. c'est a dire l'endroit ou le noeud doit etre cree

La fonction ne renvoie rien*/
	int j;dico2 *fils=NULL;//j correspond a l'indice du tableau de pointeur, il est calcule grace a la fonction convert_car

	fils=*Racine;/*On pointe sur le noeud car on va temporairement couper le "lien" qui le relie a son pere afin d'y ajouter le nouveau noeud*/
	creernoeud2(Racine);
	(**Racine).fils[5]=NULL;
	j=convert_car(lettre[i]);
	(**Racine).fils[j]=fils;
	(**Racine).debut=(*fils).debut;
	(**Racine).taille=i-(*fils).debut+1;
	(**Racine).DebutRacine=(*(**Racine).fils[j]).DebutRacine;
	(*(**Racine).fils[j]).debut=i+1;
	(*(**Racine).fils[j]).taille=(*(**Racine).fils[j]).taille-(**Racine).taille;
	(*(**Racine).fils[j]).pere=(*Racine);
	fils->pere=(*Racine)->fils[j];
	
}
int convert_car(char c) {
/*La structure utilisant un tableau de caractere, pour alleger le code on cree une fonction switch pour preciser
la case dans laquelle doit se situer le programme en fonction de la lettre*/
	switch (c)
	{
		case 'a': return 0;
		break;
		case 't': return 1;
		break;
		case 'c' : return 2;
		break;
		case 'g' : return 3;
		break;
		case '$' : return 4;
		break;
	}
	return 4;
}
